public void removeAllkey(ListNode head, int key) {
	
	if (head == null) {
		return;
	}
	
	ListNode cur = head.next;
	ListNode prev = head;
	
	while (cur != null) {
		if (cur.val == key) {
			// 删除节点
			prev.next = cur.next;
			cur = cur.next;
			
		} else {
			prev = cur;
			cur = cur.next;
		}
	}
	if (head.val == key) {
		head = head.next;
	}
}



public ListNode reverseList(ListNode head) {
	
	if (head == null) return null;
	if (head.next == null) return head;
	
	// 从头节点的后一个节点开始反转
	ListNode cur = head.next;
	
	// 反转后，头结点就一定是尾节点了 next 一定为 null
	head.next = null;
	while (cur != null) {
		//记录 cur 后面的节点
		ListNode curNext = cur.next;
		// 反转
		cur.next = head;
		// 此时 cur 变为头结点了
		head = cur;
		// cur 是要反转的节点
		cur = curNext;
	}
	
	return head;

}

public ListNode getMidNode(ListNode head) {
	
	if (head == null) return null;
	if (head.next == null) return head;
	
	ListNode slow = head;
	ListNode fast = head;
	
	while (fast != null && fast.next != null) {
		fast = fast.next.next;
		slow = slow.next;
	}
	
	return slow;
	
}

public ListNode findKthToTail(ListNode head, int k) {
	
	if (head == null || k <= 0)
		return null;
	
	ListNode fast = head;
	ListNode slow = head;

	for (int i = 0; i < k-1; i++) {
		fast = fast.next;
		if (fast == null) return null;
	}
	while (fast.next != null) {
		fast = fast.next;
		slow = slow.next;
	}
	return slow;
}

public ListNode linkeTwoList(ListNode headA,ListNode headB){
	
	ListNode newHead = new ListNode(-1);
	ListNode tmpHead = newHead;
	
	while (headA != null && headB != null) {
		if (headA.val > headB.val) {
			tmpHead.next = headB;
			headB = headB.next;
		} else {
			tmpHead.next = headA;
			headA = headA.next;
		}
		tmpHead = tmpHead.next;
	}
	
	while (headA != null) {
		tmpHead.next = headA;
	}
	while (headB != null) {
		tmpHead.next = headB;
	}
	return newHead.next;
}

public ListNode partition(ListNode head, int x) {
	
	ListNode beforeHead = null;
	ListNode beforeEnd = null;
	ListNode afterHead = null;
	ListNode afterEnd = null;
	
	ListNode cur = head;
	while (cur != null) {
		if (cur.val < x) {
			if (beforeHead == null) {
				beforeHead = beforeEnd = cur;
			} else {
				beforeEnd.next = cur;
				beforeEnd = beforeEnd.next;
			}
		} else {
			if (afterHead == null) {
				afterHead = afterEnd = cur;
			} else {
				afterEnd.next = cur;
				afterEnd = afterEnd.next;
			}
		}
		cur = cur.next;
	}
	
	
	// 如果 x 非常小
	// 小到 before 范围内没有元素
	// beforeEnd.next 会报出空指针异常
	if(beforeHead == null) 
		return afterHead;
	beforeEnd.next = afterHead;
	
	// 但如果 after 范围中，最后一个元素，并非是整个链表中值最大的节点
	// 则需要断开原链表的连接关系
	if (afterHead != null) {
		afterEnd.next = null;
	}
	
	return beforeHead;
}

public boolean chkPalindrome(ListNode head) {
	ListNode fast = head;
	ListNode slow = head;
	
	if (head == null) 
		return true;
	
	// 利用 fast 和 slow 向后动，找到中间节点
	while (fast != null && fast.next != null) {
		fast = fast.next.next;
		slow = slow.next;
	}
	
	// 此时 slow 指向的是中间节点
	// 进行反转链表
	ListNode cur = slow.next;
	while (cur != null) {
		ListNode curNext = cur.next;
		cur.next = slow;
		slow = cur;
		cur = curNext;
	}
	
	// 此时 slow 已经成为了尾节点
	while (head != slow) {
		if (head.val != slow.val) 
			return false;
		if(head.next == slow) 
			return true;
		head = head.next;
		slow = slow.next;
	}
	return true;
}


public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
	
	if (headA == null || headB == null)
		return null;
	
	int lenA = 0;
	int lenB = 0;
	int len = 0;
	ListNode pL = null;
	ListNode pS = null;
	
	pL = headA;
	pS = headB;
	
	
	while (pL != null) {
		pL = pL.next;
		lenA++;
	}
	while (pS != null) {
		pS = pS.next;
		lenB++;
	}
	len = lenA - lenB;
	pL = headA;
	pS = headB;
	
	if (len < 0) {
		pL = headB;
		pS = headA;
		len = lenB - lenA;
	}
	
	while (len != 0) {
		pL = pL.next;
		len--;
	}
	
	while (pL != pS) {
		pL = pL.next;
		pS = pS.next;
	}
	return pL;
}


public boolean hasCycle(ListNode head) {
	
	if (head == null || head.next == null) return false;
	
	ListNode fast = head;
	ListNode slow = head;
	
	while (fast != null && fast.next != null) {
		fast = fast.next.next;
		slow = slow.next;
		if (fast == slow) return true;
	}
	return false;
}

public ListNode detectCycle(ListNode head) {
	
	if (head == null || head.next == null) return null;
	
	ListNode fast = head;
	ListNode slow = head;
	
	while (fast != null && fast.next != null) {
		fast = fast.next.next;
		slow = slow.next;
		if (fast == slow) break;
	}
	
	// 非环
	if (fast == null || fast.next == null) return null;
	
	slow = head;
	
	while (slow != fast) {
		fast = fast.next;
		slow = slow.next;
	}
	return slow;
}



public ListNode deleteDuplication(ListNode pHead){
	
	ListNode newHead = new ListNode(-1);
	ListNode tmpHead = newHead;
	ListNode cur = pHead;
	while (cur != null) {
		if (cur.next != null && cur.val == cur.next.val) {
			while (cur.next != null && cur.val == cur.next.val) {
				cur = cur.next;
			}
			// 在内部循环中找到所有重复节点后，还需要cur再向后移动一位，确保跳过所有重复节点
			cur = cur.next;
		} else {
			tmpHead.next = cur;
			cur = cur.next;
			tmpHead = tmpHead.next;
		}
	}
	tmpHead.next = null;
	return newHead.next;
}